// https://leetcode.cn/problems/path-sum-ii/

// 算法思路总结：
// 1. 回溯算法收集所有路径和等于目标值的路径
// 2. 深度优先搜索遍历所有根到叶子的路径
// 3. 到达叶子节点时验证路径和，满足则保存路径
// 4. 回溯时恢复路径和与路径数组状态
// 5. 时间复杂度：O(n)，空间复杂度：O(h)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include <string>
#include "BinaryTreeUtils.h"

class Solution 
{
public:
    int sum;
    vector<int> path;
    vector<vector<int>> ret;

    vector<vector<int>> pathSum(TreeNode* root, int targetSum) 
    {
        sum = 0;
        ret.clear();

        recur(root, targetSum);

        return ret;
    }

    void recur(TreeNode* root, int targetSum)
    {
        if (root == nullptr)
        {
            return ;
        }

        sum += root->val;
        path.push_back(root->val);

        if (root->left == nullptr && root->right == nullptr)
        {
            if (sum == targetSum)
            {
                ret.push_back(path);
            }
            sum -= root->val;
            path.pop_back();
             
            return ;
        }

        recur(root->left, targetSum);
        recur(root->right, targetSum);

        sum -= root->val;
        path.pop_back();

        return ;
    }
};

int main()
{
    vector<string> tree1 = {"5","4","8","11","null","13","4","7","2","null","null","5","1"};
    vector<string> tree2 = {"1","2","3"};
    int targetSum1 = 22, targetSum2 = 5; 
    Solution sol;

    auto root1 = buildTree(tree1);
    auto root2 = buildTree(tree2);

    auto vv1 = sol.pathSum(root1, targetSum1);
    auto vv2 = sol.pathSum(root2, targetSum2);

    printResult(vv1);
    printResult(vv2);

    return 0;
}